/**
 * 给出两个链表,编写算法找到两个链表的公共结点
 */
#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
	int data;
	struct LNode* next;
}LNode, *LinkedList;

//链表初始化
bool init(LinkedList &list);

//插入元素
bool insert(LinkedList &list, int data);

//打印链表中的元素
void print(LinkedList &list);

//获取链表的长度
int length(LinkedList &list);

//寻找公共结点
void findPublicNode(LinkedList &list1, LinkedList &list2);


int main()
{
	LinkedList list1=NULL;
	init(list1);
	insert(list1,4);
	insert(list1,3);
	insert(list1,2);
	insert(list1,7);
	insert(list1,9);
	insert(list1,1);
	print(list1);
	
	LinkedList list2=NULL;
	init(list2);
	insert(list2,3);
	insert(list2,5);
	insert(list2,7);
	insert(list2,8);
	print(list2);
	printf("======\n");
	findPublicNode(list1, list2);
	return 0;
}

bool init(LinkedList &list)
{
	LNode* node=(LNode* )malloc(sizeof(LNode));
	if(!node) return false;
	node->data=-1;
	node->next=NULL;
	list=node;
	return true;
}

bool insert(LinkedList &list, int data)
{
	LinkedList node=list;
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->data=data;
	newNode->next=NULL;
	while(node->next) node=node->next;
	node->next=newNode;
	return true;
}

void print(LinkedList &list)
{
	LinkedList node=list->next;
	while(node)
	{
		printf("%d ",node->data);
		node=node->next;
	}
	printf("\n");
}

int length(LinkedList &list)
{
	LinkedList node=list->next;
	int count=0;
	while(node)
	{
		count++;
		node=node->next;
	}
	return count;
}

void findPublicNode(LinkedList &list1, LinkedList &list2)
{
	LinkedList L1=list1->next;
	LinkedList L2=list2->next;
	
	while(L1)
	{
		while(L2)
		{
			if((L2->data)==(L1->data))
			{
				printf("%d ",L2->data);
			}
			L2=L2->next;
		}
		L1=L1->next;
		L2=list2->next;     //重置L2指针的位置
	}
}